home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / man / int_set.tex < prev    next >
Encoding:
Text File  |  1994-08-05  |  1.5 KB  |  54 lines
  1. {\magonebf 3.9 Integer Sets  (int\_set)}
  2.  
  3. {\bf 1. Definition}
  4.  
  5. An instance $S$ of the data type $int\_set$ is a subset of a fixed interval 
  6. interval $[a..b]$ of the integers.
  7.  
  8. \def\name{$int\_set$}
  9. \def\type{int\_set}
  10.  
  11. \bigskip
  12. {\bf 2. Creation}
  13.  
  14. \create S (a,b)
  15.  
  16. creates an instance \var\ of type $int\_set$ for elements from $[a..b]$ and 
  17. initializes it to the empty set. 
  18.  
  19. \bigskip
  20. {\bf 2. Operations}
  21. \+\cleartabs & \hskip 1.8truecm & \hskip 6truecm &\cr
  22. \+\op void insert  {int\ x} 
  23.                             {adds $x$ to \var}
  24. \+\nop                      {\precond $a\le x\le b$.}
  25. \smallskip
  26. \+\op void del     {int\ x} 
  27.                             {deletes $x$ from \var}
  28. \+\nop                      {\precond $a\le x\le b$.}
  29. \smallskip
  30. \+\op bool member  {int\ x} 
  31.                             {returns true if $x$ in \var, false otherwise}
  32. \+\nop                      {\precond $a\le x\le b$.}
  33. \smallskip
  34. \+\op void clear   {}    
  35.                             {makes \var\ the empty set}
  36. \bigskip
  37. \+&$int\_set$  &$S1\ =\ S2$   &assignment\cr
  38. \smallskip
  39. \+&$int\_set$  &$S1\ |\ S2$   &returns the union of $S1$ and $S2$\cr
  40. \smallskip
  41. \+&$int\_set$  &$S1\ \&\ S2$  &returns the intersection of $S1$ and $S2$\cr
  42. \smallskip
  43. \+&$int\_set$  &$\tilde{}\ S$ &returns the complement of $S$\cr
  44. \smallskip
  45.  
  46.  
  47. \bigskip
  48. {\bf 3. Implementation}
  49.  
  50. Integer sets are implemented by bit vectors. Operations insert, delete,
  51. member,empty, and size take constant time. Clear, intersection, union 
  52. and complement take time $O(b-a+1)$.
  53.  
  54.